from msvcrt import getch
import os 
import sys
from datetime import datetime

starttime = datetime.now() 
 
level1= [
			['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
			['#', ' ', ' ', '*', ' ', '*', '#', '#', '#', '#', '*', ' ', '*', ' ', '*', '#', '#', '#', '*', ' ', '*', '#', ' ', '*', ' ', '#', '#', '#', '#', '#', '#', '#', '#', ' ', '*', ' ', ' ', '*', '#', '*', ' ', '*', ' ', '*', ' ', '*', ' ', ' ', '*', '#'],
			['#', '#', '#', ' ', '#', ' ', '*', ' ', '#', '*', '#', '#', '#', '*', '#', '*', '#', ' ', '#', '*', ' ', '*', '#', ' ', '*', ' ', '*', '#', '*', ' ', '*', ' ', '*', '#', '#', '#', '*', '#', '#', '#', '*', '#', '#', '#', '#', '#', '#', '#', ' ', '#'],
			['#', ' ', '#', '*', '#', '*', '#', '*', '#', ' ', '#', '*', ' ', ' ', '#', ' ', '#', '*', '#', ' ', '#', '#', '#', '#', '#', '#', ' ', '#', ' ', '#', '#', '#', '#', '#', ' ', '*', ' ', '*', ' ', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '#', '*', '#'],
			['#', '*', '#', ' ', '#', ' ', '#', ' ', '#', '*', '#', ' ', '#', '#', '#', '*', '#', ' ', '#', '*', '#', ' ', '*', '*', ' ', '#', '*', '#', '*', '#', ' ', '*', ' ', '*', '*', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '*', '#', '#', ' ', '#'],
			['#', ' ', '#', '*', '#', '*', '#', '*', '#', ' ', '#', '*', '#', '#', ' ', ' ', '#', '*', '#', ' ', '#', '*', '#', '#', '*', '#', ' ', '#', ' ', '#', '*', '#', '*', '#', '#', ' ', '*', ' ', '*', '*', '*', '*', ' ', '*', '#', ' ', '#', '#', '*', '#'],
			['#', '*', ' ', ' ', '#', ' ', '#', ' ', '#', '*', '#', ' ', '#', '#', '#', '#', ' ', ' ', '#', '#', '#', ' ', '#', '#', ' ', '*', '#', '#', '#', '#', ' ', '#', ' ', '#', ' ', '*', '#', '*', '#', ' ', '#', '#', '#', ' ', '#', '*', '#', '*', ' ', '#'],
			['#', ' ', '#', '*', '#', '#', '#', '*', '#', ' ', '#', '#', '*', '*', '*', '#', '*', '#', ' ', '*', '*', '*', ' ', ' ', '#', ' ', '#', '#', '#', '#', '*', '#', '*', '#', '*', '#', '#', ' ', '#', '*', '#', ' ', '*', '*', '#', ' ', '#', '#', '#', '#'],
			['#', '*', '#', ' ', '*', '*', '#', ' ', '#', '*', '#', '#', '*', '#', ' ', '#', ' ', '#', '*', '#', '#', '#', '#', '*', '#', '*', '#', '#', '#', '#', ' ', '#', ' ', '#', ' ', '#', '#', '*', ' ', ' ', '#', '*', '#', '#', '#', '*', '*', ' ', ' ', '#'],
			['#', ' ', '*', '#', '#', ' ', '#', '*', '*', ' ', '#', '#', ' ', '#', '*', '#', '*', '*', ' ', ' ', ' ', ' ', '#', ' ', '#', ' ', '#', ' ', '*', '*', '*', '#', '#', '#', '*', '#', '#', ' ', '#', '*', '#', ' ', '#', '#', '#', ' ', '#', '#', '*', '#'],
			['#', '#', ' ', '#', '#', '*', '#', ' ', '#', '*', ' ', '*', '*', '#', ' ', '#', '#', ' ', '#', '#', '#', '*', '#', '*', '#', '*', '#', '*', '#', '#', ' ', '#', '#', ' ', ' ', '#', '#', '*', '#', ' ', '#', '*', ' ', ' ', ' ', '*', '#', ' ', ' ', '#'],
			['#', '#', '#', '#', '#', ' ', ' ', '*', '#', '#', '#', '#', '#', '#', '*', '#', '#', '*', '#', '*', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '*', '#', '#', '*', '*', ' ', ' ', ' ', '#', '#', '#', '#', '*', '#', '#', ' ', '#', '*', '#', '#'],
			['#', '*', ' ', '*', ' ', '*', '#', ' ', '#', '#', '#', '#', '#', '#', ' ', '#', ' ', ' ', '#', ' ', '*', '*', '#', '*', '#', '*', '#', '*', '#', '*', '#', '#', '#', ' ', ' ', '#', '#', '#', '#', '#', '#', '#', ' ', '#', '#', '*', '#', ' ', ' ', '#'],
			['#', ' ', '#', '#', '#', '#', '#', '*', ' ', '#', '*', ' ', ' ', '#', '*', '#', '#', '#', '#', '#', '#', '#', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#', '*', '*', '#', '*', '*', ' ', '#', '#', '#', '*', '#', '*', ' ', '#', '#', '*', '#'],
			['#', '*', '#', '#', '#', '#', '#', '#', '#', '#', ' ', '#', '*', '#', ' ', '#', '*', '*', '*', '*', ' ', ' ', '*', '*', '#', '*', '*', '*', '#', '*', '#', '*', '#', ' ', ' ', '#', ' ', '#', '*', '*', ' ', ' ', ' ', '#', ' ', '*', ' ', '*', ' ', '#'],
			['#', ' ', '*', ' ', '*', ' ', '*', ' ', '*', ' ', '*', '#', ' ', '#', '*', '#', ' ', '#', '#', '#', '#', '#', '#', ' ', '*', '#', ' ', '#', '#', ' ', '*', ' ', '#', '#', '#', '#', '*', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '*', '#'],
			['#', '#', ' ', '#', '#', '#', '#', '#', ' ', '#', '#', '#', '*', '*', ' ', '#', '*', '#', ' ', ' ', '*', '#', '#', '*', '#', '#', '*', '#', ' ', '#', '#', '#', ' ', '*', ' ', '#', ' ', '#', ' ', '*', '*', '#', ' ', '*', '*', ' ', '*', ' ', ' ', '#'],
			['#', '#', '*', '#', '*', '*', ' ', '#', '*', '#', ' ', '*', '#', '#', '#', '#', ' ', ' ', '#', '#', ' ', '*', ' ', ' ', '#', '#', ' ', '#', '*', '#', ' ', '*', '*', '#', '*', '#', '*', '#', '*', '#', ' ', '#', '*', '#', '#', '#', '#', '#', '*', '#'],
			['#', '#', ' ', '#', ' ', '#', '*', '#', ' ', '#', '*', '#', '#', '#', '#', '#', '#', '*', '#', '#', '*', '#', '#', '#', '#', '#', '*', '#', ' ', '*', '*', '#', ' ', '#', ' ', '*', ' ', '#', ' ', '#', '*', '#', ' ', ' ', '*', '*', ' ', '#', ' ', '#'],
			['#', '#', '*', '#', '*', '#', ' ', '#', '*', '*', ' ', ' ', ' ', '*', '*', '*', '*', ' ', '*', '*', ' ', ' ', '#', '#', '#', '#', ' ', '#', '#', '#', '#', '#', '*', '#', '*', '#', '#', '#', '*', '#', ' ', '*', '#', '#', '#', '#', '*', '#', '*', '#'],
			['#', '*', ' ', '*', ' ', '#', '*', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', ' ', '#', '#', '*', '#', '#', '#', '#', '*', ' ', '*', ' ', '#', ' ', ' ', '#', ' ', ' ', '*', ' ', ' ', '#', '#', ' ', '*', '*', ' ', '#', ' ', '*', ' ', '#'],
			['#', ' ', '#', '#', '#', '#', ' ', '#', '#', ' ', '*', '*', '*', '#', '#', ' ', ' ', '*', '*', '#', '#', ' ', '#', '*', ' ', '#', '#', '#', '#', '*', '#', '#', '*', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '*', '#', '#', '#', '*', '#'],
			['#', '*', '#', '#', '#', '#', '*', '#', '#', '*', '#', '#', ' ', '#', '#', '*', '#', '#', ' ', ' ', '#', '*', '#', ' ', '#', ' ', ' ', '*', '#', ' ', '#', '#', ' ', '#', ' ', '*', ' ', '*', ' ', ' ', '*', '*', ' ', '#', ' ', '#', '#', '#', ' ', '#'],
			['#', ' ', '#', '*', '*', ' ', ' ', '#', '#', ' ', '#', '#', '*', '#', '#', ' ', '*', ' ', '#', '*', '#', ' ', '#', '*', '#', '*', '#', ' ', ' ', '*', '*', '*', '*', '#', ' ', '#', '#', '#', '#', '#', '#', '#', '*', '#', '*', '#', ' ', '#', '*', '#'],
			['#', '*', '#', ' ', '#', '*', '#', '#', ' ', '*', '#', '#', ' ', '#', '#', '#', '#', '#', '#', '#', '#', '*', '#', ' ', '#', ' ', '#', '*', '#', '#', '#', '#', ' ', ' ', ' ', '#', '*', ' ', '*', '*', ' ', '#', ' ', '#', ' ', '#', '*', '#', ' ', '#'],
			['#', ' ', '#', '*', '#', ' ', '*', '#', '*', '#', '*', ' ', '*', '#', ' ', '*', ' ', '*', '*', ' ', '#', ' ', '#', '*', '#', '#', '*', ' ', '#', ' ', '#', '#', '*', '#', ' ', '#', ' ', '#', '#', '#', '*', '#', '*', '#', '*', '#', ' ', '#', '*', '#'],
			['#', '*', ' ', ' ', '#', '#', '#', '#', ' ', ' ', '#', '#', '#', '#', '*', '#', '#', '#', '#', '*', '#', '*', '#', '#', '#', '#', ' ', '#', '#', '*', ' ', '#', ' ', '#', ' ', '#', '*', '#', '*', ' ', '#', '#', ' ', '#', ' ', '#', '*', '#', ' ', '#'],
			['#', ' ', '#', '*', ' ', '*', ' ', '*', '*', '*', '*', ' ', ' ', ' ', ' ', '#', '#', '#', '#', ' ', '*', ' ', '#', '#', '#', '#', '*', '#', '#', '#', '#', ' ', '#', '#', ' ', '#', ' ', '#', ' ', '*', ' ', ' ', '*', '#', '*', '#', ' ', '#', '*', ' ', ' ', ' ','End'],
			['#', '*', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', ' ', '*', '*', ' ', '*', '*', '#', '#', ' ', '#', '*', '#', '#', '#', '#', '#', '#', '#', ' ', '#', '*', '#', '#', '#'],
			['#', ' ', '*', ' ', '*', ' ', '*', ' ', ' ', ' ', ' ', '*', '*', '*', '*', ' ', '*', ' ', ' ', '*', ' ', '*', '*', ' ', '*', '*', '*', '#', '#', '#', ' ', ' ', '*', '*', ' ', '#', ' ', '*', '*', ' ', '*', '*', ' ', ' ', '*', '*', ' ', '*', ' ', '#'],
			['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
		]
level2=[
			['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
			['#', ' ', '*', ' ', '#', '*', ' ', '*', ' ', '*', ' ', '*', ' ', '*', ' ', '#', '#', '#', '#', '#', '#', '#', '#', '*', ' ', '*', '#', ' ', 'Q', '#', '*', '*', ' ', '#', '#', '*', '#', '*', '#', '*', ' ', '*', ' ', '*', ' ', '*', '#', '*', 'Q', '#'],
			['#', '#', '#', '*', '#', ' ', '#', '#', '#', '#', '#', '#', '#', '#', '*', ' ', '*', ' ', '*', ' ', '*', ' ', '*', ' ', '#', ' ', '#', '*', '#', '#', ' ', '#', '*', ' ', ' ', 'Q', '#', ' ', '#', '#', '#', '#', '#', '#', '#', ' ', '*', ' ', '#', '#'],
			['#', ' ', 'Q', ' ', '#', '*', '*', ' ', '*', ' ', '#', ' ', '*', 'Q', ' ', '#', '#', '#', ' ', '#', '#', '#', '#', '*', '#', '*', '*', ' ', ' ', '*', '*', '#', '#', '#', '*', '#', ' ', '*', '*', ' ', '*', ' ', '*', ' ', '*', '#', '#', '#', '#', '#'],
			['#', '*', '#', '*', '#', '#', '#', '#', '#', '*', '#', '*', '#', '#', '*', '#', '#', '*', '*', '#', ' ', '*', '#', ' ', '#', ' ', '#', '#', '#', '#', ' ', '#', ' ', '*', ' ', '#', '*', '#', ' ', '#', '#', '#', '#', '#', ' ', '#', ' ', '*', ' ', '#'],
			['#', ' ', '#', ' ', '#', ' ', ' ', '*', ' ', ' ', '#', '#', '#', '#', ' ', '#', '#', '#', ' ', '#', '*', '#', '#', '*', '#', '*', '#', '#', '*', ' ', 'Q', '#', '*', '#', '#', '#', ' ', '#', '*', '#', ' ', '*', ' ', '#', '*', '#', '*', '#', '*', '#'],
			['#', '*', '#', '*', '#', '*', '#', '#', 'Q', '#', '*', ' ', ' ', '#', '*', '#', ' ', '*', '*', '#', ' ', ' ', '*', ' ', '#', ' ', '#', '*', ' ', '#', '#', '#', ' ', '#', '#', '#', '#', '#', ' ', '#', '*', '#', '*', '*', ' ', '#', ' ', '#', ' ', '#'],
			['#', ' ', '#', ' ', '#', ' ', '*', '#', '#', '#', ' ', '#', '*', '#', ' ', '#', '*', '#', '#', '#', '#', '#', '#', '#', '#', '*', '#', ' ', '#', '*', '*', ' ', '*', ' ', '*', '#', '*', ' ', '*', '*', ' ', '#', ' ', '#', '*', '*', '*', '#', '*', '#'],
			['#', '*', 'Q', '*', '#', '#', ' ', ' ', '*', '#', '*', '#', '#', '*', '*', '#', ' ', '#', '#', '#', '#', '*', '#', '*', '*', ' ', '*', '*', '#', ' ', '#', '#', ' ', '#', '#', '#', ' ', '#', ' ', '#', '#', '#', '*', '#', ' ', '#', '#', '#', ' ', '#'],
			['#', ' ', '#', ' ', '#', '#', '*', '#', ' ', '#', ' ', '#', '#', ' ', '#', '#', '*', ' ', '*', '*', '#', ' ', '#', ' ', '#', '#', '#', ' ', '#', '*', '#', '#', '*', '*', ' ', '#', '*', '#', '*', ' ', '*', ' ', '#', '#', '*', '#', ' ', '*', '*', '#'],
			['#', '*', '#', '*', '#', '#', ' ', '#', '*', '#', '*', '#', 'Q', '*', '#', '#', 'Q', '#', '#', ' ', '#', '*', '#', '*', '#', '#', '#', '*', '#', ' ', ' ', '*', '#', '#', '*', '#', ' ', '#', '#', '#', '#', '*', '#', '#', ' ', '*', '*', '#', '#', '#'],
			['#', ' ', '#', '*', ' ', '*', '*', '#', ' ', '#', ' ', '#', '#', ' ', '#', '#', ' ', '#', '#', '*', '#', ' ', '#', ' ', '*', '*', '*', ' ', '#', '#', '#', ' ', '#', ' ', ' ', '#', '*', '#', ' ', '*', '#', ' ', ' ', '#', '*', '#', ' ', ' ', ' ', '#'],
			['#', '*', '#', ' ', '#', '#', '#', '#', '*', '#', '*', '*', '#', '*', '#', '#', '#', '#', '#', ' ', '#', '*', '#', '*', '#', '#', '#', '*', '*', '*', '#', '*', '#', '*', '#', '#', ' ', '#', '#', ' ', '#', '#', '#', '#', ' ', '#', '#', '#', '*', '#'],
			['#', ' ', '#', '*', '#', '#', ' ', '*', 'Q', '#', '#', ' ', '#', ' ', '#', '*', '*', '*', ' ', ' ', '#', ' ', '#', ' ', '#', ' ', '#', '#', '#', '#', '#', ' ', '#', ' ', ' ', '*', '*', '#', '#', '*', ' ', '*', '*', ' ', '*', '#', ' ', '*', ' ', '#'],
			['#', '*', '#', ' ', ' ', ' ', '*', '#', '#', '#', '#', '*', '#', '*', '#', ' ', '#', '#', '#', '#', '#', '*', '#', '*', ' ', '*', '#', '*', ' ', '*', '#', '*', '#', '#', '*', '#', ' ', '#', '#', '#', '#', '#', '#', '#', '#', '#', '*', '#', '*', '#'],
			['#', ' ', '*', '#', '#', '#', '#', '#', '#', '#', '#', ' ', '#', ' ', '#', '*', '#', '#', '#', '*', '*', ' ', '#', '#', '#', ' ', '*', ' ', '#', ' ', '*', ' ', '#', '*', ' ', '#', '*', '#', '*', ' ', '*', ' ', ' ', '*', '#', '*', ' ', '#', 'Q', '#'],
			['#', '#', ' ', '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '#', '*', '#', ' ', '*', ' ', '*', ' ', '#', '#', '#', ' ', '*', '#', '#', '#', '#', '*', '#', '*', '#', ' ', '#', '#', ' ', '#', ' ', '#', '#', '#', '#', ' ', '#', ' ', '#', '#', ' ', '#'],
			['#', '#', '#', '#', '#', '#', '#', '*', '#', '#', '#', '#', '#', ' ', '#', '#', '#', '*', '#', '#', '#', '#', '#', '*', ' ', '*', ' ', '*', 'Q', ' ', '#', ' ', ' ', '*', '#', '#', '*', '#', '*', '#', ' ', '*', '#', '*', ' ', '*', ' ', ' ', '*', '#'],
			['#', '*', '*', ' ', ' ', '#', '#', ' ', '#', '#', '#', '#', '#', '*', ' ', '#', '#', ' ', '#', '*', ' ', '*', '*', ' ', '#', '#', '#', '#', '#', '#', '#', '*', '#', ' ', ' ', '#', ' ', '#', ' ', '#', '*', '#', '#', '#', '#', '#', '*', '#', ' ', '#'],
			['#', ' ', '#', '#', ' ', ' ', '*', '*', '*', ' ', '*', '#', '#', '#', '*', '#', '*', ' ', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', ' ', '#', '#', '*', '#', '*', '#', '*', ' ', ' ', ' ', '*', ' ', '*', ' ', 'Q', '#', '*', '#'],
			['#', '*', '#', '#', '#', '#', '#', ' ', '#', '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', '#', '#', ' ', '*', ' ', '*', '*', '*', ' ', '*', ' ', '*', '*', ' ', '*', '#', '#', ' ', ' ', ' ', '#', '#', '*', '#', '#', '#', '#', '#', '*', '#', '#', ' ', '#'],
			['#', ' ', '#', '*', ' ', '*', '#', '*', '#', '#', '#', '#', '*', '#', '#', '#', '*', '*', '#', '*', '#', '*', '#', '#', '#', '#', '#', '#', '#', '#', '#', ' ', '#', '#', '*', '#', '*', '#', ' ', ' ', '#', '*', ' ', '*', ' ', ' ', '#', '#', '*', '#'],
			['#', '*', '#', ' ', '#', ' ', '#', ' ', '#', '*', '*', '*', ' ', '*', '*', '#', '#', ' ', '#', ' ', '#', ' ', '#', ' ', ' ', '*', ' ', '#', '#', '#', '#', '*', '*', '#', ' ', '#', ' ', '*', '#', '#', '#', ' ', '#', '#', '#', '#', '*', '*', ' ', '#'],
			['#', ' ', ' ', '*', '#', '*', '#', '*', '*', ' ', '#', ' ', '#', '#', '#', '#', ' ', '*', '#', '*', '#', '*', '*', '*', '#', '#', '*', '*', ' ', '*', '*', '#', ' ', '#', '*', '*', '#', '#', '*', '*', '#', '*', '*', ' ', '*', '#', ' ', '#', '*', '#'],
			['#', '#', '*', '#', '#', ' ', '#', '#', '#', '#', '#', '*', '*', ' ', ' ', '#', '*', '#', '#', ' ', '#', ' ', '#', ' ', '*', '#', ' ', '#', '*', '#', '#', '#', '*', '#', '#', ' ', '#', '#', '#', ' ', '#', ' ', '#', '#', ' ', '#', '*', '#', ' ', '#'],
			['#', '#', ' ', '#', '#', '*', '*', ' ', ' ', '*', '#', '#', '#', '#', '#', '#', '#', '#', '#', '*', '#', '*', '#', '#', ' ', '#', '*', '#', ' ', '#', ' ', '*', ' ', '#', '#', '*', '#', '#', '#', '*', '*', '*', '#', '#', '*', '#', ' ', '#', '*', '#'],
			['#', '#', '*', ' ', ' ', '#', '#', '#', '#', ' ', '*', ' ', ' ', '*', '*', '*', ' ', '*', '*', ' ', '#', ' ', '#', '#', '*', ' ', ' ', '#', '*', '#', '*', '#', '#', '*', '#', ' ', '*', ' ', ' ', '#', '#', '#', ' ', '*', ' ', '#', '*', '*', '#', '#'],
			['#', '#', '#', '#', ' ', '#', ' ', '*', '*', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '*', '#', '#', ' ', '#', '*', '*', '#', '#', ' ', '*', '*', ' ', '#', '#', ' ', '#', '#', '*', ' ', '#', '*', '#', '#', '#', '#', '#', ' ', ' ', ' ', ' ', 'End'],
			['#', '*', ' ', '*', ' ', ' ', '*', '#', ' ', '#', '#', '#', '*', ' ', ' ', '*', '*', ' ', '*', '#', '*', ' ', '#', '*', '*', '#', ' ', '#', '#', '#', '#', '#', '#', '#', ' ', '#', '*', '#', '*', ' ', '*', '#', ' ', ' ', '*', '*', ' ', ' ', '*', '#'],
			['#', ' ', '#', '#', '#', '#', '#', '#', '*', '*', ' ', '*', ' ', '#', '#', '#', '#', '*', '#', '#', ' ', '#', '#', ' ', '#', '#', '*', ' ', ' ', '*', '*', ' ', ' ', '*', '*', '#', ' ', '*', ' ', '#', ' ', '*', '#', '#', '#', '#', '#', '#', '#', '#'],
			['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
		]
		
level3=[
			['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
			['#', ' ', '*', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', ' ', '*', ' ', '*', ' ', '*', 'Q', '*', ' ', '*', 'Q', 'Q', '*', ' ', ' ', '*', ' ', '*', ' ', '*', ' ', 'Q', 'Q', 'Q', ' ', '*', ' ', '*', ' ', 'Q', 'Q', '*', '*', ' ', '*', '#'],
			['#', '*', 'Q', '*', ' ', 'Q', '*', ' ', '*', ' ', 'Q', '*', ' ', ' ', '*', 'Q', '*', 'Q', '*', 'Q', '*', ' ', 'Q', ' ', 'Q', '*', ' ', 'Q', '*', ' ', 'Q', 'Q', 'Q', 'Q', '*', ' ', '*', ' ', '*', 'Q', 'Q', 'Q', '*', 'Q', '*', ' ', 'Q', 'Q', ' ', '#'],
			['#', ' ', 'Q', 'Q', '*', 'Q', ' ', 'Q', 'Q', '*', 'Q', 'Q', '*', 'Q', ' ', 'Q', ' ', 'Q', ' ', ' ', 'Q', 'Q', 'Q', '*', ' ', ' ', 'Q', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', '*', 'Q', 'Q', ' ', 'Q', '*', 'Q', ' ', 'Q', ' ', 'Q', '*', 'Q', '*', '#'],
			['#', '*', '*', ' ', ' ', 'Q', '*', 'Q', 'Q', ' ', 'Q', 'Q', ' ', 'Q', '*', 'Q', '*', ' ', 'Q', '*', 'Q', '*', '*', ' ', 'Q', 'Q', '*', '*', '*', '*', ' ', '*', '*', ' ', 'Q', ' ', '*', 'Q', '*', 'Q', ' ', '*', '*', 'Q', '*', '*', ' ', 'Q', ' ', '#'],
			['#', ' ', ' ', 'Q', '*', 'Q', ' ', 'Q', 'Q', '*', 'Q', 'Q', '*', 'Q', ' ', 'Q', 'Q', '*', 'Q', ' ', 'Q', ' ', 'Q', '*', '*', '*', ' ', 'Q', 'Q', ' ', 'Q', 'Q', 'Q', '*', 'Q', 'Q', ' ', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', '#'],
			['#', 'Q', '*', 'Q', ' ', 'Q', '*', 'Q', 'Q', ' ', 'Q', 'Q', ' ', 'Q', '*', 'Q', 'Q', ' ', 'Q', '*', 'Q', '*', 'Q', 'Q', 'Q', 'Q', 'Q', '*', ' ', '*', 'Q', '*', 'Q', ' ', 'Q', '*', '*', 'Q', '*', 'Q', '*', '*', ' ', '*', '*', ' ', '*', '*', '*', '#'],
			['#', 'Q', ' ', 'Q', '*', 'Q', ' ', 'Q', 'Q', '*', ' ', '*', '*', 'Q', 'Q', ' ', ' ', '*', 'Q', ' ', 'Q', ' ', '*', ' ', ' ', ' ', 'Q', ' ', 'Q', 'Q', 'Q', ' ', 'Q', '*', 'Q', ' ', 'Q', 'Q', ' ', 'Q', ' ', 'Q', 'Q', 'Q', ' ', 'Q', 'Q', 'Q', ' ', '#'],
			['#', 'Q', '*', 'Q', ' ', 'Q', '*', 'Q', 'Q', ' ', 'Q', 'Q', ' ', 'Q', 'Q', '*', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', '*', '*', 'Q', '*', '*', '*', ' ', 'Q', '*', 'Q', ' ', 'Q', '*', ' ', 'Q', '*', 'Q', '*', 'Q', '*', ' ', '*', 'Q', '*', ' ', '*', '#'],
			['#', 'Q', ' ', 'Q', '*', 'Q', ' ', 'Q', '*', 'Q', 'Q', 'Q', '*', '*', 'Q', ' ', 'Q', '*', 'Q', '*', '*', '*', 'Q', ' ', 'Q', '*', ' ', 'Q', 'Q', '*', '*', ' ', 'Q', '*', 'Q', 'Q', '*', 'Q', ' ', 'Q', ' ', ' ', 'Q', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', '#'],
			['#', '*', '*', '*', 'Q', 'Q', '*', 'Q', ' ', 'Q', '*', 'Q', 'Q', ' ', 'Q', '*', 'Q', ' ', 'Q', ' ', 'Q', ' ', 'Q', '*', 'Q', ' ', 'Q', ' ', ' ', ' ', ' ', 'Q', 'Q', ' ', ' ', ' ', 'Q', 'Q', '*', 'Q', 'Q', '*', 'Q', 'Q', '*', '*', ' ', '*', 'Q', '#'],
			['#', ' ', 'Q', ' ', 'Q', '*', 'Q', '*', '*', '*', ' ', 'Q', 'Q', '*', 'Q', ' ', 'Q', '*', 'Q', '*', 'Q', '*', 'Q', ' ', ' ', '*', 'Q', '*', 'Q', '*', 'Q', '*', '*', '*', 'Q', 'Q', '*', '*', ' ', 'Q', 'Q', ' ', ' ', ' ', 'Q', 'Q', 'Q', ' ', 'Q', '#'],
			['#', '*', 'Q', '*', 'Q', ' ', 'Q', ' ', 'Q', ' ', 'Q', '*', '*', ' ', 'Q', '*', '*', 'Q', 'Q', ' ', 'Q', ' ', 'Q', 'Q', 'Q', ' ', 'Q', ' ', 'Q', ' ', 'Q', ' ', 'Q', 'Q', '*', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', '*', 'Q', ' ', ' ', ' ', 'Q', '*', 'Q', '#'],
			['#', ' ', 'Q', ' ', 'Q', '*', 'Q', '*', 'Q', '*', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', ' ', 'Q', 'Q', '*', 'Q', '*', ' ', 'Q', '*', '*', 'Q', '*', 'Q', '*', 'Q', '*', ' ', '*', ' ', 'Q', '*', 'Q', '*', '*', '*', ' ', 'Q', 'Q', 'Q', '*', 'Q', ' ', 'Q', '#'],
			['#', '*', 'Q', 'Q', ' ', ' ', 'Q', ' ', 'Q', ' ', 'Q', '*', ' ', 'Q', 'Q', 'Q', '*', 'Q', 'Q', ' ', 'Q', 'Q', '*', '*', 'Q', ' ', 'Q', ' ', 'Q', ' ', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', ' ', '*', 'Q', ' ', 'Q', 'Q', 'Q', ' ', '*', ' ', 'Q', '*', 'Q', '#'],
			['#', ' ', '*', 'Q', '*', 'Q', ' ', '*', 'Q', '*', 'Q', ' ', 'Q', '*', ' ', ' ', ' ', 'Q', 'Q', '*', 'Q', 'Q', ' ', 'Q', '*', '*', 'Q', 'Q', 'Q', '*', 'Q', '*', '*', ' ', '*', ' ', '*', 'Q', ' ', '*', ' ', '*', 'Q', '*', 'Q', 'Q', 'Q', ' ', 'Q', '#'],
			['#', 'Q', ' ', '*', ' ', 'Q', '*', 'Q', 'Q', ' ', '*', '*', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', ' ', 'Q', '*', '*', ' ', 'Q', ' ', 'Q', '*', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', ' ', 'Q', ' ', ' ', '*', 'Q', '*', 'Q', '#'],
			['#', 'Q', '*', 'Q', 'Q', ' ', ' ', 'Q', 'Q', '*', 'Q', ' ', 'Q', '*', 'Q', 'Q', 'Q', 'Q', '*', '*', 'Q', ' ', 'Q', 'Q', 'Q', '*', 'Q', ' ', '*', '*', '*', ' ', ' ', '*', ' ', 'Q', '*', '*', '*', ' ', '*', '*', 'Q', 'Q', 'Q', ' ', 'Q', ' ', 'Q', '#'],
			['#', 'Q', ' ', 'Q', 'Q', '*', 'Q', 'Q', 'Q', ' ', 'Q', '*', 'Q', ' ', '*', '*', '*', '*', ' ', 'Q', 'Q', '*', ' ', '*', ' ', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', '*', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', ' ', 'Q', ' ', '*', ' ', 'Q', '*', 'Q', '#'],
			['#', 'Q', '*', 'Q', '*', ' ', 'Q', 'Q', 'Q', '*', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', '*', '*', '*', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', '*', ' ', ' ', ' ', 'Q', '*', ' ', ' ', 'Q', '*', '*', ' ', '*', ' ', '*', 'Q', '*', 'Q', 'Q', 'Q', ' ', 'Q', '#'],
			['#', '*', ' ', 'Q', ' ', 'Q', '*', ' ', '*', ' ', 'Q', '*', ' ', 'Q', ' ', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', '*', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', '*', 'Q', ' ', 'Q', '*', 'Q', ' ', 'Q', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', '*', '*', 'Q', '#'],
			['#', ' ', 'Q', ' ', '*', 'Q', 'Q', 'Q', ' ', 'Q', 'Q', 'Q', '*', 'Q', 'Q', '*', ' ', '*', ' ', ' ', ' ', 'Q', ' ', 'Q', '*', '*', '*', 'Q', '*', '*', ' ', '*', '*', ' ', ' ', 'Q', '*', ' ', 'Q', '*', '*', ' ', '*', ' ', ' ', 'Q', ' ', 'Q', 'Q', '#'],
			['#', '*', 'Q', '*', 'Q', '*', ' ', '*', '*', 'Q', 'Q', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', '*', 'Q', '*', 'Q', '*', '*', ' ', 'Q', ' ', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', '*', 'Q', '*', ' ', 'Q', '*', ' ', 'Q', 'Q', 'Q', 'Q', '*', 'Q', '*', ' ', '*', '#'],
			['#', ' ', '*', ' ', 'Q', ' ', 'Q', 'Q', ' ', '*', '*', ' ', '*', '*', '*', ' ', 'Q', ' ', ' ', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', '*', 'Q', 'Q', 'Q', '*', '*', 'Q', ' ', 'Q', ' ', 'Q', 'Q', 'Q', '*', 'Q', '*', 'Q', 'Q', ' ', 'Q', ' ', 'Q', ' ', '#'],
			['#', 'Q', 'Q', 'Q', 'Q', '*', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', '*', 'Q', '*', 'Q', 'Q', '*', 'Q', ' ', ' ', ' ', 'Q', ' ', 'Q', '*', ' ', ' ', ' ', 'Q', '*', 'Q', '*', '*', '*', ' ', ' ', 'Q', ' ', '*', '*', ' ', 'Q', '*', 'Q', 'Q', '#'],
			['#', '*', ' ', '*', ' ', ' ', 'Q', '*', '*', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', ' ', 'Q', ' ', 'Q', '*', ' ', 'Q', '*', 'Q', '*', 'Q', '*', 'Q', ' ', 'Q', 'Q', '*', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', ' ', '*', '*', '#'],
			['#', ' ', 'Q', 'Q', 'Q', 'Q', '*', ' ', 'Q', '*', '*', '*', ' ', 'Q', '*', '*', 'Q', '*', 'Q', ' ', 'Q', 'Q', ' ', 'Q', ' ', '*', ' ', 'Q', '*', '*', 'Q', ' ', 'Q', ' ', '*', ' ', 'Q', '*', '*', '*', '*', '*', ' ', ' ', 'Q', 'Q', 'Q', 'Q', ' ', 'Q'],
			['#', '*', '*', 'Q', '*', '*', ' ', 'Q', 'Q', ' ', 'Q', 'Q', '*', 'Q', ' ', 'Q', 'Q', ' ', 'Q', '*', 'Q', ' ', '*', 'Q', 'Q', 'Q', 'Q', 'Q', 'Q', ' ', 'Q', '*', 'Q', '*', 'Q', '*', 'Q', ' ', 'Q', 'Q', 'Q', 'Q', 'Q', '*', 'Q', 'Q', '*', 'Q', ' ', '*', ' ', ' ', 'End'],
			['#', 'Q', ' ', '*', ' ', 'Q', 'Q', 'Q', 'Q', '*', 'Q', ' ', ' ', 'Q', '*', 'Q', 'Q', '*', 'Q', ' ', '*', '*', 'Q', 'Q', '*', ' ', '*', ' ', 'Q', '*', 'Q', ' ', '*', ' ', 'Q', ' ', 'Q', '*', 'Q', ' ', 'Q', 'Q', 'Q', ' ', 'Q', '*', ' ', 'Q', 'Q', 'Q'],
			['#', 'Q', 'Q', 'Q', 'Q', ' ', '*', '*', ' ', ' ', 'Q', '*', 'Q', 'Q', ' ', ' ', '*', ' ', 'Q', 'Q', 'Q', ' ', ' ', '*', ' ', 'Q', 'Q', '*', ' ', ' ', 'Q', '*', ' ', 'Q', 'Q', '*', '*', ' ', 'Q', '*', '*', ' ', '*', '*', '*', ' ', 'Q', 'Q', 'Q', '#'],
		    ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
		]
			
class Board:
	def __init__(self,board, endx, endy):
		self.board =board
		self.endx =endx
		self.endy =endy
	
	def setPosition(self, x, y, ch):
	
		self.board[x][y] = ch
	def getPosition(self, x, y):
		return self.board[x][y]
	
	def printBoard(self):
		for row in self.board:
			for col in row:
				sys.stdout.write(col)
			print
		print "\nScore: ", player.score
		print "\nTimer: ", 120 - (datetime.now() - starttime).seconds
class Player:
	def __init__(self):
		self.pchar = 'P'
		self.x = 1
		self.y = 1
		self._x = self.x
		self._y = self.y
		self.score = 0
		
	
	def move(self):
		
		self._x = self.x
		self._y = self.y
		
		moved = True
		key = ord(getch())
		if key == 72 and board.getPosition(player.x - 1, player.y) != "#": #Up
			if board.getPosition(player.x - 1, player.y) == 'Q':
					player.x = 1
					player.y = 1
			if board.getPosition(player.x -1, player.y) == '*':
				player.score += 5
			self.x -= 1
			player.pchar = '^'
		elif key == 80 and board.getPosition(player.x + 1, player.y) != "#": #Down
			if board.getPosition(player.x +1, player.y) == 'Q':
					player.x = 1
					player.y = 1
			if board.getPosition(player.x +1, player.y) == '*':
				player.score += 5
			self.x += 1
			player.pchar = 'v'
		elif key == 75 and board.getPosition(player.x, player.y - 1) != "#": #Left
			if board.getPosition(player.x, player.y -1) == 'Q':
					player.x = 1
					player.y = 1
			if board.getPosition(player.x, player.y -1) == '*':
				player.score += 5
			self.y -= 1
			player.pchar = '<'
		elif key == 77 and board.getPosition(player.x, player.y + 1) != "#": #Right
			if board.getPosition(player.x, player.y +1) == 'Q':
					player.x = 1
					player.y = 1
			if board.getPosition(player.x, player.y +1) == '*':
				player.score += 5
			self.y += 1
			player.pchar = '>'
		elif key == 27: #ESC
			exit()
		else:
			moved = False
		
		return moved

def clearScreen():
	os.system("cls")


player = Player()
board = Board(level1, 27, 52)
clearScreen()
board.setPosition(player.x, player.y, ">")
board.printBoard()
starttime = datetime.now() 
while True:
	moved = player.move()
	if moved:
		clearScreen()
		board.setPosition(player._x, player._y, " ")
		board.setPosition(player.x, player.y, player.pchar)
		board.printBoard()
	if (datetime.now() - starttime).seconds >= 120: 
		print "Time's up"
		exit()
	if player.x == board.endx and player.y == board.endy:
		break

clearScreen()
print 'Congrats, you finished the first level. Now you may continue...'
board = Board(level2, 27, 52)
player.x = 1
player.y = 1
board.setPosition(player.x, player.y, ">")
board.printBoard()
starttime = datetime.now() 
while True:
	moved = player.move()
	if moved:
		clearScreen()
		board.setPosition(player._x, player._y, " ")
		board.setPosition(player.x, player.y, player.pchar)
		board.printBoard()
	if (datetime.now() - starttime).seconds >= 120: 
		print "Time's up"
		exit()
	if player.x == board.endx and player.y == board.endy:
		break
			
			
clearScreen()
print 'Good job! Go on to the final level...'
board = Board(level3, 27, 52)
player.x = 1
player.y = 1
board.setPosition(player.x, player.y, ">")
board.printBoard()
starttime = datetime.now() 
while True:
	moved = player.move()
	if moved:
		clearScreen()
		board.setPosition(player._x, player._y, " ")
		board.setPosition(player.x, player.y, player.pchar)
		board.printBoard()
	if (datetime.now() - starttime).seconds >= 120: 
		print "Time's up"
		exit()
	if player.x == board.endx and player.y == board.endy:
		break
print 'Excellent! You have just completed all three levels!!!'